Motivation
流量分配(impression allocation)是电商平台的核心问题之一.主流的流量分配做法一般将其视为一个信息检索问题或者推荐问题.代表性的方法是建模一个CTR(Click-Through-Rate)模型来给每个商品打分，然后通过分数的高低来进行流量分配.
这些模型主要关注短期回报，没有考虑长期回报.另外这还会导致商品的更新迭代的速度变慢，例如商品的冷启动周期会变长.这篇论文提出一个基于强化学习的流量分配模型，同时考虑了短期回报和长期回报，也降低了商品的更新迭代周期.
Product Lifecycle Model
通过观测商品CTR历史变化趋势，可以将商品划分4个阶段：
- Introduction: Also known as market development - this is when a new product is first brought to market. Sales are low and creep along slowly.
- Growth: Demand begins to accelerate and the size of the total market expands rapidly.
- Maturaty: Demand levels off and grows.
- Decline: The product begins to lose consumer appeal and sales drift downward.
通过强化学习的试错(trial-and-error),模型能够在introduction阶段提前发现潜在的爆款，也能够在decline阶段发现滞销商品，从而加速了更新迭代周期(metabolism)，提高了流量利用效率.
在第$t$步，每个商品表示为$x_t \in \mathbb{R}^d$,$d$为商品的特征维度，商品所处的潜在生命周期为$z_t \in \mathcal{L}$,其中$\mathcal{L} = { 0,1,2,3 }$. $p_t \in \mathbb{R}$代表CTR,$q_t \in \mathbb{R}$代表商品累积的流量.此时分配的流量为$u_t \in \mathbb{R}$，那么:
$$
\begin{cases}
q_{t+1} = q_t + u_t\\
p_{t+1} = p_t + f(z_t,q_t)\\
z_{t+1} = \mathcal{g}(x_t,z_t,t)
\end{cases}
$$
其中，$f$为$p$的导数，$\mathcal{g}$为状态转移函数.论文中有详细介绍其计算公式.商品生命周期的状态转移如下图所示：
A SCALABLE REINFORCEMENT MECHANISM DESIGN FRAMEWORK
在上述场景中，每一步平台观测所有商品的全局信息，然后通过观测和策略给商品分配流量，这样每个商品的特征和生命周期会发生变化.然后平台能通过反馈来评价这次分配的好坏.下面形式化定义上述过程.
state
我们将平台的全局信息作为状态：
$$ s = [x_1,x_2,\dots,x_n]^T \in \mathbb{R}^{n \times d} $$
action
我们将商品特征的权重作为action，这样的好处就是避免了维度过大.
$$ a = \pi (s|\theta^{\mu}) \in \mathbb{R}^d$$
那么我们可以进一步计算每个商品的分数：
$$ o_i = \frac{1}{1 + e^{-a^Tx_i}}, \forall i \in {1,2,\dots,n} $$
每个商品要分配流量可以通过下面来得到：
$$ u_i = \frac{e^{o_i}}{\sum_i^{n}e^{o_i}}, \forall i \in {1,2,\dots,n}$$
reward
reward的定义如下：
$$ R(s,a) = \frac{1}{n}\sum\limits_i^n\left[\frac{1}{t_i}\int_{t=0}^{t_i}p(t)\frac{dq(t)}{dt}dt\right]$$
其含义为最大化平台所有商品在其生命周期内的期望点击量.可以近似为：
$$ R(s,a) \approx \frac{1}{n}\sum\limits_i^{n}\frac{1}{t_i}\sum\limits_{\tau=0}^{t_i}p_\tau^iu_\tau^i$$
issues
由于平台的商品量极大，所以要采样一部分商品来表示平台的状态：
$$\hat{s} = [x_1,x_2,\dots,x_{n_s}]^T \in \mathbb{R}^{n_s \times d}$$
这样会导致两个问题：
- 采样的$n_s$个商品应该如何排序来保持排序不变性(permutation invariance).
- 如何减少采样带来的偏置，特别是$n_s$元小于$n$时.
对于问题1论文提出利用PCA对特征降维来进行排序;对于问题2论文提出repeated sampling based Experiences Genaration算法来解决.论文有细节描述，这里不再展开.
The Results
商品的四个生命周期时间随着训练变化的趋势如下图：
从图中我们能看出随着训练进行decline阶段周期明显下降，这能够避免平台的流量浪费.
下图展示了和CTR模型相比三个指标的变化，我们可以看到平均点击增加了6%，商品成长到maturity时期的时间降低了26%，这意味着商品迭代周期明显加速.